package com.algorithm.lesson_06;

import java.util.HashMap;

public class CopyListWithRandom {
	public static Node copyListWithRandByHashMap(Node head) {
		HashMap<Node, Node> map = new HashMap<>();
		Node cur = head;

		// 将原始链表的节点和新建的链表节点保存到HashMap中，原始节点作为key，新建节点作为value
		while (cur != null) {
			map.put(cur, new Node(cur.value));
			cur = cur.next;
		}

		cur = head;

		while (cur != null) {
			// 顺序连接
			map.get(cur).next = map.get(cur.next);
			// 随机连接
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}

		return map.get(head);
	}

	public static Node copyListWithRandomByAddCopyNode(Node head) {

		Node cur = head;
		Node curCopy = null;

		// 在原节点的后面再加一个copy节点
		// 1->1'->2->2'->3->3'
		while (cur != null) {
			// 新建copy节点
			curCopy = new Node(cur.value);
			// 将当前节点的后面节点连接到copy节点的后面
			curCopy.next = cur.next;
			// 将copy节点连接到cur节点的后面
			cur.next = curCopy;
			// 将当前节点重置为下一个未拷贝节点
			cur = curCopy.next;
		}

		cur = head;
		while (cur != null) {
			curCopy = cur.next;
			// 将当前节点的rand节点的copy节点连接到当前copy节点
			curCopy.rand = cur.rand != null ? cur.rand.next : null;
			cur = curCopy.next;
		}

		cur = head;
		Node res = head.next;

		while (cur != null) {
			curCopy = cur.next;
			Node next = curCopy.next;// 可能为null
			cur.next = next;
			curCopy.next = next != null ? next.next : null;
			cur = next;
		}

		return res;
	}

	public static void printRandomLinkedList(Node head) {
		Node cur = head;
		// 输出顺序链接表
		System.out.print("order:");
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.next;
		}
		System.out.println();

		cur = head;

		// 输出随机链接表
		System.out.print("rand:");
		while (cur != null) {
			System.out.print(cur.rand == null ? "null " : cur.rand.value + " ");
			cur = cur.next;
		}
		System.out.println();
	}
}
